๋ฌธ์
Programmers - ํฉ์น ํ์ ์๊ธ
๐ Logic
private static int[] dijkstra(int start) {
int[] costs = new int[n + 1];
Arrays.fill(costs, Integer.MAX_VALUE);
Queue<Edge> queue = new PriorityQueue<>();
queue.add(new Edge(start, 0));
costs[start] = 0;
while(!queue.isEmpty()) {
Edge node = queue.poll();
int now = node.dest;
int weight = node.weight;
// ํ์ฌ ๋น์ฉ๋ณด๋ค ๋ ํฐ ๊ฒฝ์ฐ๋ ํจ์ค
if (weight > costs[now]) continue;
// ํ์ฌ ์ ์ ์์ ๊ฐ ์ ์๋ ์ฃ์ง ๋ฆฌ์คํธ
ArrayList<Edge> edges = adjList[now];
for (Edge e : edges) {
// ํ์ฌ(now) ์ ์ ๊น์ง์ ๋น์ฉ๊ณผ ๋ค์์ผ๋ก ์ด๋ํ ์ฃ์ง์ ๋น์ฉ์ ํฉ
int cost = costs[now] + e.weight;
// ์ด์ ๋น์ฉ๋ณด๋ค ์๋ก์ด ๋น์ฉ์ด ๋ ์์ ๊ฒฝ์ฐ ๊ฐฑ์
if (cost < costs[e.dest]) {
costs[e.dest] = cost;
queue.add(new Edge(e.dest, cost));
}
}
}
return costs;
}
- ๋ค์ต์คํธ๋ผ ์๊ณ ๋ฆฌ์ฆ์ ์ฌ์ฉํด ์ฃผ์ด์ง ๊ธฐ์ ์ ๊ธฐ์ค์ผ๋ก ๊ฐ ์ง์ ๊น์ง์ ์ต์ ๋น์ฉ์ ๊ตฌํ๊ณ , ์ด๋ฅผ ๋ฐํํ๋ค.
๐ CODE
์ฝ๋ ๋ณด๊ธฐ/์ ๊ธฐ๐ซ
import java.util.*;
class Edge implements Comparable<Edge> {
int dest;
int weight;
public Edge(int dest, int weight) {
this.dest = dest;
this.weight = weight;
}
// ๋ค์ต์คํธ๋ผ ์๊ณ ๋ฆฌ์ฆ ์ฌ์ฉ์ ์ํด ๋น์ฉ ๊ธฐ์ค ์ค๋ฆ์ฐจ์ ์ ๋ ฌ
@Override
public int compareTo(Edge n) {
return this.weight - n.weight;
}
}
// ๊ฐ ์ง์ ๊น์ง์ ์ต์ ๊ฑฐ๋ฆฌ๋ฅผ ๊ตฌํ๋ค.
// ์ดํ 1 ~ N๊น์ง์ ์ง์ ์ ํฉ์น ์ง์ ์ผ๋ก ๋๊ณ , ์ต์ ๋น์ฉ์ ๊ตฌํ๋ค.
class Solution {
static ArrayList<Edge>[] adjList;
static int n;
public int solution(int n, int s, int a, int b, int[][] fares) {
this.n = n;
init(fares);
// S๋ฅผ ๊ธฐ์ ์ผ๋ก ์ต์ ๋น์ฉ ๊ณ์ฐ
int[] startFromSrc = dijkstra(s);
// A๋ฅผ ๊ธฐ์ ์ผ๋ก ์ต์ ๋น์ฉ ๊ณ์ฐ
int[] startFromA = dijkstra(a);
// B๋ฅผ ๊ธฐ์ ์ผ๋ก ์ต์ ๋น์ฉ ๊ณ์ฐ
int[] startFromB = dijkstra(b);
int answer = Integer.MAX_VALUE;
for (int i = 1; i <= n; i++)
// i๋ ํฉ์น ์ง์
// src๋ก๋ถํฐ i๊น์ง์ ์ต์ ๋น์ฉ + i๋ก๋ถํฐ a๊น์ง์ ์ต์ ๋น์ฉ + i๋ก๋ถํฐ b๊น์ง์ ์ต์ ๋น์ฉ
answer = Math.min(answer, startFromSrc[i] + startFromA[i] + startFromB[i]);
return answer;
}
// ์ธ์ ๋ฆฌ์คํธ ์์ฑ ๋ฐ ์ด๊ธฐํ
private static void init(int[][] fares) {
adjList = new ArrayList[n + 1];
for (int i = 1; i < n + 1; i++)
adjList[i] = new ArrayList<>();
for (int[] fare : fares) {
adjList[fare[0]].add(new Edge(fare[1], fare[2]));
adjList[fare[1]].add(new Edge(fare[0], fare[2]));
}
}
private static int[] dijkstra(int start) {
int[] costs = new int[n + 1];
Arrays.fill(costs, Integer.MAX_VALUE);
Queue<Edge> queue = new PriorityQueue<>();
queue.add(new Edge(start, 0));
costs[start] = 0;
while(!queue.isEmpty()) {
Edge node = queue.poll();
int now = node.dest;
int weight = node.weight;
// ํ์ฌ ๋น์ฉ๋ณด๋ค ๋ ํฐ ๊ฒฝ์ฐ๋ ํจ์ค
if (weight > costs[now]) continue;
// ํ์ฌ ์ ์ ์์ ๊ฐ ์ ์๋ ์ฃ์ง ๋ฆฌ์คํธ
ArrayList<Edge> edges = adjList[now];
for (Edge e : edges) {
// ํ์ฌ(now) ์ ์ ๊น์ง์ ๋น์ฉ๊ณผ ๋ค์์ผ๋ก ์ด๋ํ ์ฃ์ง์ ๋น์ฉ์ ํฉ
int cost = costs[now] + e.weight;
// ์ด์ ๋น์ฉ๋ณด๋ค ์๋ก์ด ๋น์ฉ์ด ๋ ์์ ๊ฒฝ์ฐ ๊ฐฑ์
if (cost < costs[e.dest]) {
costs[e.dest] = cost;
queue.add(new Edge(e.dest, cost));
}
}
}
return costs;
}
}
โ๏ธ Review
- source๊ฐ ์ฃผ์ด์ง๊ณ , ๊ฐ ์ง์ ๊น์ง์ ์ต์ ๋น์ฉ์ ๊ตฌํ๋ Single Source Shortest Path ๋ฌธ์ ๋ผ๋ ๊ฒ์ ์ฝ๊ฒ ์ ์ ์์๊ณ , ๋ค์ต์คํธ๋ผ ์๊ณ ๋ฆฌ์ฆ์ ์ฌ์ฉํ๋ค.
-
๋ค๋ง, ํฉ์น ์ง์ ์ด๋ผ๋ ์กฐ๊ฑด์ ๋ํด ๋งํ๋ค.
S -> X,X -> A,X -> B์์ X๊ฐ 1 ~ N ์ง์ ์ด ๊ฐ๋ฅํ๋ค๋ ์์ด๋์ด๊ฐ ์ฃผ์ํ๋ค.